
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2049. -- [Sdoi2008]Cave 洞穴勘测
</title><center><h2>2049: [Sdoi2008]Cave 洞穴勘测
</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>360&nbsp;&nbsp;<span class=green>Solved: </span>164<br>[<a href='submitpage.php?id=2049'>Submit</a>][<a href='problemstatus.php?id=2049'>Status</a>][<a href='bbs.php?id=2049'>Discuss</a>]</center><h2>Description</h2><div class=content>
辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。
洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：
如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v
如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v
经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。
然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。
辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。
已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。
</div><h2>Input</h2><div class=content>第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。
以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。
</div><h2>Output</h2><div class=content>对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）
 </div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
样例输入1 cave.in<br />
200	5<br />
Query	123	127<br />
Connect	123	127<br />
Query	123	127<br />
Destroy	127	123<br />
Query	123	127<br />
样例输入2 cave.in<br />
<br />
3 	5<br />
Connect	1	2<br />
Connect	3	1<br />
Query	2	3<br />
Destroy	1	3<br />
Query	2	3<br />
<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>样例输出1 cave.out<br />
No<br />
Yes<br />
No<br />
<br />
<br />
样例输出2 cave.out<br />
<br />
Yes<br />
No<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>数据说明<br />
<br />
10%的数据满足n≤1000, m≤20000<br />
20%的数据满足n≤2000, m≤40000<br />
30%的数据满足n≤3000, m≤60000<br />
40%的数据满足n≤4000, m≤80000<br />
50%的数据满足n≤5000, m≤100000<br />
60%的数据满足n≤6000, m≤120000<br />
70%的数据满足n≤7000, m≤140000<br />
80%的数据满足n≤8000, m≤160000<br />
90%的数据满足n≤9000, m≤180000<br />
100%的数据满足n≤10000, m≤200000<br />
<br />
保证所有Destroy指令将摧毁的是一条存在的通道<br />
本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2049'>Submit</a>][<a href='problemstatus.php?id=2049'>Status</a>][<a href='bbs.php?id=2049'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
